def maxSubArrayDp(nums):
    length = len(nums)
    if length == 0:
        return 0
    elif length == 1:
        return nums[0]
    else:
        return max(maxSubArrayDp(nums[:length-1]),maxSubArrayDp(nums[:length-1])+nums[-1])
def main():
    # nums = [-2,1,-3,4,-1,2,1,-5,4]
    nums = [-2,1,-3,4,-1,2,1,-5,4]
    for i in range(1,len(nums)):
        print(i,maxSubArrayDp(nums[:i]))
if __name__ == "__main__":
    main()